/**
 * Created by losor on 2017/3/24.
 */
public class _69_Sqrtx {

    public static void main(String[] args) {
        _69_Sqrtx a = new _69_Sqrtx();
        System.out.println(a.mySqrt(2));
    }

    public int mySqrt(int x) {
        long sum = 0;
        for (int i = 0; i <= x; i++) {
            if (sum > x){
                return i-1;
            }
            sum = sum + 2*i + 1;
        }
        return x;
    }

    public int mySqrtbt(int x) {
        if (x == 0)
            return 0;
        int left = 1;
        int right = x;
        while(true){
            int mid = left + (right - left)/2;
            if (mid > x/mid){
                right = mid - 1;
            }
            else {
                if (mid + 1 > x/(mid + 1))
                    return mid;
                left = mid + 1;
            }
        }
    }
}
